// @algorithm @lc id=1000238 lang=cpp
// @title IDBivT

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> ans;
    string temp;
    vector<string> generateParenthesis(int n) {
        dfs(0, 0, n);
        return ans;
    }
    void dfs(int left_cnt, int right_cnt, int n) {
        if (left_cnt == n && right_cnt == n) {
            ans.push_back(temp);
            return;
        }
        if (right_cnt > left_cnt) {
            return;
        }
        if (left_cnt < n) {
            temp.push_back('(');
            dfs(left_cnt + 1, right_cnt, n);
            temp.pop_back();
        }
        if (right_cnt < n) {
            temp.push_back(')');
            dfs(left_cnt, right_cnt + 1, n);
            temp.pop_back();
        }
        return;
    }
};